package base_Suanfa.erchashu;

import java.util.Arrays;

public class DijkstraAlgothrim {
    public static void main(String[] args) {
        int min=32767;
        char vertex[]={ 'A','B','C','D','E','F','G'};
        int matrix[][]={{0,7,min,5,min,min,min},{7,0,8,9,7,min,min},{min,8,0,min,5,min,min},{5,9,min,0,15,6,min},{min,7,5,15,0,8,9},{min,min,min,6,8,0,11},{min,min,min,min,9,11,0}};
  Graph2 graph2=new Graph2(vertex,matrix);
  graph2.showGraph(graph2);
  Dijkstra dijkstra=new Dijkstra();
  dijkstra.DijkstraDemo(vertex,matrix,1);
    }
}
class Graph2{
    private char vertexs[];  //存放顶点
    private  int matrix[][];  //邻接矩阵

    public Graph2(char[] vertexs, int[][] matrix) {
        this.vertexs = vertexs;
        this.matrix = matrix;
    }
    public void showGraph(Graph2 graph) {
        for (int edge[] : graph.matrix) {
            System.out.println(Arrays.toString(edge));
        }
    }
}
class Dijkstra{
    public void DijkstraDemo(char vertexs[],int matrix[][],int start){
     int n=vertexs.length;
     //保存起始点到各个顶点的最短路径
     int  bis[]=new int[n];
     //记录是否被访问
     int isVisited[]=new int[n];
     //记录最短路径结点
        String []path=new String[n];
        //假定初始标记点可以到达图中所有点
        for(int i=0;i<n;i++){
            path[i]=new String(vertexs[start]+"-->"+vertexs[i]);
        }
        //第一个顶点已经被访问
      bis[start]=0;
        isVisited[start]=1;
        //进行n-1次遍历
        for(int i=1;i<n;i++){
            //作为一个中间连接点
            int u=-1;
            //寻找最小1权值，默认无穷大
            int minDis=Integer.MAX_VALUE;
            //找到当前原点到所以点中最短路径，并记录下标
            for(int j=0;j<n;j++){
                if(isVisited[j]==0&&matrix[start][j]<minDis){
                    minDis=matrix[start][j];
                    u=j;
                }
            }
            bis[u]=minDis;
            isVisited[u]=1;
            //以u为中介点，找到其他最短路径w(u,v)
            for(int k=0;k<n;k++){
                if(isVisited[k]==0&&matrix[start][u]+matrix[u][k]<matrix[start][k]){
                        matrix[start][k]=matrix[start][u]+matrix[u][k];
                        path[k]=path[u]+"-->"+vertexs[k];
                }
            }
        }
        for(int i=0;i<n;i++){
            System.out.println(path[i]+"的最短路径为:"+bis[i]);
        }
    }
}
